package com.Algorithm.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author shkstart
 * @create 2021-08-19 16:13
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //创建hashmap集合，存储电视台和覆盖地点
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        //创建hashset,包含地方电视台
        //HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<String>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<String>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");


        HashSet<String> hashSet4 = new HashSet<String>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<String>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        //加入到map
        broadcasts.put("k1",hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);
        //存放电台覆盖地区的集合
        HashSet<String> allAreas=new HashSet<String>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        //存放被选中电视台
        ArrayList<String> selects = new ArrayList<>();
        //存放选中的电视台与总的电视台的交集
        HashSet<String> tempSet=new HashSet<String>();
        //如果allAreas集合为空，那就说明选择结束
        //定义一个maxKep，指向一次循环中最大的一个电视台
        String maxKey=null;
        while (allAreas.size()!=0){
            //遍历一次，清空一次
            maxKey=null;
            //开始遍历
              for (String key:broadcasts.keySet()){
                  //每一次遍历，应该将temset清空
                  tempSet.clear();
                  //电视台对应的集合
                  HashSet<String> areas = broadcasts.get(key);
                  //将查到的集合存储到交集中
                  tempSet.addAll(areas);
                  //找到他们的交集
                  tempSet.retainAll(allAreas);
                  //计算temset的个数，并且与前一次进行比较，取覆盖地区比较多的进行存储--贪心算法
                  if (tempSet.size()>0&&(maxKey==null||tempSet.size()>broadcasts.get(maxKey).size())){
                      //取到最大的
                      maxKey=key;
                  }

                  }
                  //maxley不为空，那就取到
            if (maxKey!=null){
                  //添加电视台的集合
                selects.add(maxKey);
                //从总集合中取出覆盖的地区
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }

        System.out.println("得到的选择的结果"+selects);
    }
}
